package q701_insertIntoBST;

import CommonClass.Common.TreeNode;
public class Solution_2 {
    /*
    用递归的方式来解决该题
    我们可以通过使用图例来了解递归的操作
    假设一开始只有一个节点，那么就能够直接得到答案
    而多个节点则是在一个节点的基础上反复往上递归的结果
    也就是将一个节点的答案连接到了多个节点上
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 如果传入root为空，就直接返回该节点
        // 或者说节点就插入到这个位置
        if (root == null) {
            return new TreeNode(val);
        }
        // 如果root值大于val 则往左搜索找节点插入的位置
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        // 小于则往右
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }
}
